import itertools as it
import math
import timeit

def combinations(n, k):
    if n < k:
        raise ValueError("n must be at least as big as k")

    cur = 2 ** k - 1
    num_threes = 0
    num_subsets = math.factorial(n) / (math.factorial(k) * math.factorial(n - k))
    for itr in range(int(num_subsets)):
        yield cur
        for low_index in range(0, n - 1):               # scan the number looking for a 0b01, and count all the 0b11's
            mask = 3 << low_index                       # mask is 0b11
            masked = (cur & mask) >> low_index          # push the result right so we can do equality operations
            if masked == 3:                             # count the 0b11's so we know how many 1's to reset
                num_threes += 1
            if masked == 1:
                cur |= 1 << low_index + 1               # promote a 1
                cur &= ~((1 << (low_index + 1)) - 1)    # clear the lower bits
                cur |= (1 << num_threes) - 1            # reset the rest of the 1's
                num_threes = 0
                break


if __name__ == '__main__':
    def wrap():
        for combo in it.combinations(range(20), 6):
            pass

    def wrap2():
        for x in combinations(20, 6):
            pass

    print(timeit.timeit(wrap, number=1))
    print(timeit.timeit(wrap2, number=1))
